.TH bigint 3 "28 July 2000"
.SH NAME
bigint - large integer package
.SH DESCRIPTION
.PP
This library lets you do math on arbitrarily large integers.
It's reasonably fast - compared with the multi-precision routines in the "bc"
calculator program, these routines are from two to ten times faster,
except for division which is maybe half as fast.
Compared with a more finely-tuned package such as gmp, it's probably
somewhat slower.
Top speed isn't actually the point of this package, though.
The interesting aspects are:
.IP API
See the section below on the unique calling convention used by this package.
.IP Division
The multi-precision division algorithm used here is apparently a new invention.
It's not real fast, but it's very simple.
.IP License
This package uses a Berkeley-style license, which lets you do more than
the restrictive Gnu license on the gmp package.
.SH API
.PP
The calling convention is a little unusual.
There's a basic problem with writing a math library in a language that
doesn't do automatic garbage collection - what do you do about
intermediate results?
You'd like to be able to write code like this:
.nf
    d = bi_sqrt(bi_add(bi_multiply(x,x),bi_multiply(y,y)));
.fi
That works fine when the numbers being passed back and forth are
actual values - ints, floats, or even fixed-size structs.
However, when the numbers can be any size, as in this package, then you have
to pass them around as pointers to dynamically-allocated objects.
Those objects have to get de-allocated after you are done with them.
But how do you de-allocate the intermediate results in a complicated
multiple-call expression like the above?
.PP
There are two common solutions to this problem.
One, switch all your code to a language that provides automatic garbage
collection, for example Java.
This is a fine idea and I recommend you do it wherever it's feasible.
Two, change your routines to use a calling convention that prevents people
from writing multiple-call expressions like that.
The resulting code will be somewhat clumsy-looking, but it will work
just fine.
.PP
This package uses a third method, which I haven't seen used anywhere before.
It's simple: each number can be used precisely once, after which it is
automatically de-allocated.
This handles the anonymous intermediate values perfectly.
Named values still need to be copied and freed explicitly.
Here's the above example using this convention:
.nf
    d = bi_sqrt(bi_add(
            bi_multiply(bi_copy(x),bi_copy(x)),
            bi_multiply(bi_copy(y),bi_copy(y))));
    bi_free(x);
    bi_free(y);
.fi
Or, since the package contains a square routine, you could just write:
.nf
    d = bi_sqrt(bi_add(bi_square(x),bi_square(y)));
.fi
This time the named values are only being used once, so you don't
have to copy and free them.
.PP
This really works, however you do have to be very careful when writing
your code.
If you leave out a bi_copy() and use a value more than once, you'll get
a runtime error about "zero refs" and a SIGFPE.
Run your code in a debugger, get a backtrace to see where the call was,
and then eyeball the code there to see where you need to add the bi_copy().
.SH ROUTINES
Here's a list of all the routines available in the package.
.IP "bi_initialize"
Initialize the bigint package.
You must call this when your program starts up.
.IP "bi_terminate"
Shut down the bigint package.
You should call this when your program exits.
It's not actually required, but it does do some consistency
checks which help keep your program bug-free, so you really ought
to call it.
.IP "bi_no_check"
Run in unsafe mode, skipping most runtime checks.
Slightly faster.
Once your code is debugged you can add this call after bi_initialize().
.IP "bi_copy"
Make a copy of a bigint.
You must call this if you want to use a bigint more than once.
(Or you can make the bigint permanent.)
Note that this routine is very cheap - all it actually does is
increment a reference counter.
.IP "bi_permanent"
Make a bigint permanent, so it doesn't get automatically freed when
used as an operand.
.IP "bi_depermanent"
Undo bi_permanent().
The next use will free the bigint.
.IP "bi_free"
Explicitly free a bigint.
Normally bigints get freed automatically when they are used as an operand.
This routine lets you free one without using it.
If the bigint is permanent, this doesn't do anything, you have to depermanent
it first.
.IP "bi_compare"
Compare two bigints.
Returns -1, 0, or 1.
.IP "int_to_bi"
Convert an int to a bigint.
.IP "str_to_bi"
Convert a string to a bigint.
.IP "bi_to_int"
Convert a bigint to an int.
.IP "bi_print"
Write a bigint to a file.
.IP "bi_scan"
Read a bigint from a file.
.PP
Operations on a bigint and a regular int.
.IP "bi_int_add"
Add an int to a bigint.
.IP "bi_int_subtract"
Subtract an int from a bigint.
.IP "bi_int_multiply"
Multiply a bigint by an int.
.IP "bi_int_divide"
Divide a bigint by an int.
.IP "bi_int_rem"
Take the remainder of a bigint by an int, with an int result.
.IP "bi_int_mod"
Take the modulus of a bigint by an int, with an int result.
Note that mod is not rem: mod is always within [0..m), while
rem can be negative.
.PP
Basic operations on two bigints.
.IP "bi_add"
Add two bigints.
.IP "bi_subtract"
Subtract one bigint from another.
.IP "bi_multiply"
Multiply two bigints.
.IP "bi_divide"
Divide one bigint by another.
.IP "bi_rem"
Take the remainder of one bigint by another.
.IP "bi_mod"
Take the modulus of one bigint by another.
Note that mod is not rem: mod is always within [0..bim), while rem can be
negative.
.PP
Some less common operations.
.IP "bi_negate"
Negate a bigint.
.IP "bi_abs"
Absolute value of a bigint.
.IP "bi_half"
Divide a bigint in half.
.IP "bi_double"
Multiply a bigint by two.
.IP "bi_square"
Square a bigint.
.IP "bi_power"
Raise bi to the power of biexp.
.IP "bi_sqrt"
Integer square root.
.IP "bi_factorial"
Factorial.
.PP
Some predicates.
.IP "bi_is_odd"
1 if the bigint is odd, 0 if it's even.
.IP "bi_is_even"
1 if the bigint is even, 0 if it's odd.
.IP "bi_is_zero"
1 if the bigint equals zero, 0 if it's nonzero.
.IP "bi_is_one"
1 if the bigint equals one, 0 otherwise.
.IP "bi_is_negative"
1 if the bigint is less than zero, 0 if it's zero or greater.
.PP
Now we get into the esoteric number-theory stuff used for cryptography.
.IP "bi_mod_power"
Modular exponentiation.
Much faster than bi_mod(bi_power(bi,biexp),bim).
Also, biexp can be negative.
.IP "bi_mod_inverse"
Modular inverse.
mod( bi * modinv(bi), bim ) == 1.
.IP "bi_random"
Produce a random number in the half-open interval [0..bi).
You need to have called srandom() before using this.
.IP "bi_gcd"
Greatest common divisor of two bigints.
Euclid's algorithm.
.IP "bi_egcd"
Greatest common divisor of two bigints, plus the corresponding multipliers.
Extended Euclid's algorithm.
.IP "bi_lcm"
Least common multiple of two bigints.
.IP "bi_jacobi"
The Jacobi symbol.
.IP "bi_is_probable_prime"
Probabalistic prime checking.
A non-zero return means the probability that bi is prime is at
least 1 - 1/2 ^ certainty.
.IP "bi_generate_prime"
Random probabilistic prime with the specified number of bits.
.IP "bi_bits"
Number of bits in the number.
The log base 2, approximately.
.SH "SEE ALSO"
bi_bc(1), bi_factor(1)
.SH AUTHOR
Copyright � 2000 by Jef Poskanzer <jef@mail.acme.com>. All rights reserved.
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
